package class_1;

import java.util.Arrays;

public class Coding_mergesort2 {
	//请用递归和非递归方法实现。
	//阐述一下归并排序的思想。
	//
	public static void mergeSort(int[] nums) {
		/*write code here! */
	}
	public static void mergeSort2(int[] arr) {
		int n = arr.length;
		//step分组数， step为1，说明左右区间各有一个数（除非区间已经越界， 则相应调整）
		//先两两分组， 再以4个为一组， 8个为一组...直到单次分组已经超过数组总的元素个数就终止。
		for (int l, m, r, step = 1; step < n; step <<= 1) {
			l = 0;
			//后面就是讨论区间
			while (l < n) {
				//确定区间的中间下标
				m = l + step - 1;
				//判断右边界是否存在
				if (m + 1 >= n) {
					//无右侧， 不用后续merge了。
					break;//不存在说明单层的归并排序结束。
				}
				//求右边界
				r = Math.min(l + (step << 1) - 1, n - 1);
				
				//确定好了，l,m,r的值，进行合并
				merge(arr, l, m, r);
				//内层while循环进行调整
				l = r + 1;
			}
		}
	}
	public static void merge(int[] arr,int l, int m,int r) {
		int a = l;
		int b = m+1;
		int[] help = new int[r-l+1];
		int i = 0;
		while(a<=m && b<=r) {
			help[i++] = arr[a]<=arr[b]?arr[a++]:arr[b++];
		}
		
		while(a<=m) {
			help[i++] = arr[a++];
		}
		
		while(b<=r) {
			help[i++] = arr[b++];
		}
		
		for(i=l;i<=r;i++) {
			arr[i] = help[i-l];
		}
	}
	
	//测试用例。
	public static void main(String[] args) {
		int[] arr= {4,1,6,23,8,9,11,0,2,3,4,4,4,4,10};
		System.out.println("排序前:"+Arrays.toString(arr));
		mergeSort(arr);
		System.out.println("排序后："+Arrays.toString(arr));
	}
	/**
	 * output：
	 * 排序前:[4, 1, 6, 23, 8, 9, 11, 0, 2, 3, 4, 4, 4, 4, 10]
	 * 排序后：[0, 1, 2, 3, 4, 4, 4, 4, 4, 6, 8, 9, 10, 11, 23]
	 */
}
